/**
 * 143. 重排链表
 * https://leetcode-cn.com/problems/reorder-list/
 */
public class Solutions_143 {
    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4};  // {1, 4, 2, 3}
        int[] arr = {1, 2, 3, 4, 5};  // {1, 5, 2, 4, 3}

        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        reorderList(head);
        System.out.println(MyLinkedListUtils.ListNodeToString(head));
    }

    public static void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        // 寻找中间节点（偶数长度时，所在中间结点保证前面是奇数个结点，后面是偶数个结点）
        ListNode mid = middleNode(head);
        // 中间结点及之前为一个链表，中间结点之后的为一个链表
        ListNode node1 = head;
        ListNode node2 = mid.next;
        // 分割链表，两个链表之间不再有关联
        mid.next = null;
        // 翻转链表
        node2 = reverseList(node2);
        // 合并链表
        mergeList(node1, node2);
    }

    public static void mergeList(ListNode node1, ListNode node2) {
        ListNode temp_node1, temp_node2;
        while (node1 != null && node2 != null) {
            temp_node1 = node1.next;
            temp_node2 = node2.next;
            // 使 node1 的后继节点为 node2
            node1.next = node2;
            node1 = temp_node1;
            // 使 node2 的后继节点为原本的 node1 的下一结点，两个链表产生关系
            node2.next = node1;
            node2 = temp_node2;
        }
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }

    public static ListNode middleNode(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
